#include <iostream>
#include <cstdlib>

using std::rand;
using std::srand;


int initx, inity, finalx, finaly;



void mazeGenerator( char m[13][13], int * initx, int * inity, int * finalx,
        int * finaly )
{
    int i, j, x, y;

    // Coloca '.' em todos os caminhos
    for( i = 0; i < 12; i++ )
        strcpy( m[i], "............" );

    // Sorteia entrada e saida do labirinto
    *initx = rand() % 11;
    *inity = rand() % 11;
    *finalx = rand() % 11;
    *finaly = rand() % 11;

    // Sorteia 40 locais para ganhar '#'
    for( i = 0; i < 40; i++ )
    {
        x = rand() % 11;
        y = rand() % 11;
        while( ( x == *initx && y == *inity ) ||
               ( x == *finalx && y == *finaly ) )
        {
            x = rand() % 11;
            y = rand() % 11;
        }
        m[x][y] = '#';
    }
}



void printMaze( char m[13][13] )
{
    // Imprime inicio e fim do labirinto
    printf("(%d,%d) -> (%d,%d):\n", initx, inity, finalx, finaly );

    // Imprime a posicao corrente do labirinto
    int i;
    for( i = 0; i < 13; i++)
    {
        printf( "%s\n", m[i] );
    }
    printf("\n");
}



bool mazeTraverse( char m[13][13], int posx, int posy )
{
    // Se a posicao eh uma parede, aborte a busca
    if( m[posx][posy] == '#' || m[posx][posy] == 'X' )
        return false;

    // Verifica os limites do labirinto
    if( posx < 0 || posx > 11 )
        return false;
    if( posy < 0 || posy > 11 )
        return false;

    // Mostra o labirinto atual
    m[posx][posy] = 'X';
    printMaze( m );

    // Se a posicao eh a saida do labirinto, aborte busca
    if( posx == finalx && posy == finaly )
        return true;

    // Tentar buscar direita
    if( mazeTraverse(m, posx, posy + 1 ) )
        return true;

    // Tenta buscar a frente
    if( mazeTraverse(m, posx - 1, posy ) )
        return true;

    // Tenta buscar a esquerda
    if( mazeTraverse(m, posx, posy - 1 ) )
        return true;

    // Tenta buscar pra tras
    if( mazeTraverse(m, posx + 1, posy ) )
        return true;

    return false;
}



int main()
{
/* Labirinto do Livro
char maze[13][13] = { {"############"},
                      {"#...#......#"},
                      {"..#.#.####.#"},
                      {"###.#....#.#"},
                      {"#....###.#.."},
                      {"####.#.#.#.#"},
                      {"#..#.#.#.#.#"},
                      {"##.#.#.#.#.#"},
                      {"#........#.#"},
                      {"######.###.#"},
                      {"#......#...#"},
                      {"############"}
};
*/

    // seta a semente aleatoria
    srand( time( 0 ) );

    // Cria um labirinto aleatorio
    char maze[13][13];
    mazeGenerator( maze, &initx, &inity, &finalx, &finaly );

    // posicao inicial do labirinto
    bool solve = mazeTraverse( maze, initx, inity );
    if( solve )
        printf("Encontrou saida\n");
    else
        printf("Nao achou uma saida\n");

	return 0;
}

